from tools_algorithm import *


class Solution:
    def getMaximumNumber(self, moles: List[List[int]]) -> int:
        moles.sort(key=lambda a: a[0])
        print(moles)

        def ij(i, j):
            return i * 3 + j

        dirt = [(1, 0), (0, 1), (-1, 0), (0, -1)]

        def bfs(i, j):
            visit = [-1] * 9
            visit[ij(i, j)] = 0
            q = deque([(i, j)])
            while q:
                a, b = q.popleft()
                for x, y in dirt:
                    tx, ty = a + x, b + y
                    txy = ij(tx, ty)
                    if tx >= 0 and tx < 3 and ty >= 0 and ty < 3 and visit[txy] == -1:
                        visit[txy] = visit[ij(a, b)] + 1
                        q.append((tx, ty))
            return visit

        dist = [[] for _ in range(9)]
        for i in range(3):
            for j in range(3):
                dist[ij(i, j)] = bfs(i, j)
        dp = [[] for _ in range(9)]
        for i in range(9):
            dp[i].append([0, -inf])
        dp[4][0][1] = 0
        ans = 0
        for i, (t, x, y) in enumerate(moles):
            id = ij(x, y)
            mx = 0
            for j in range(9):
                td = dist[j][id]
                for k in range(len(dp[j]) - 1, -1, -1):
                    if dp[j][k][0] <= t - td:
                        mx = max(mx, dp[j][k][1] + 1)
                        break
                # if t - td >= 0:
                #     k = bisect_right(dp[j], t - td, key=lambda a: a[0]) - 1
                #     mx = max(mx, dp[j][k][1] + 1)
            if mx > 0:
                dp[id].append([t, mx])
            ans = max(ans, mx)
        return ans


cs = [
    [[0, 1, 0], [0, 0, 1], [0, 2, 1], [0, 1, 2], [0, 0, 2], [1, 2, 2], [1, 0, 0]],
    # [[4, 2, 1], [1, 1, 2], [2, 1, 0], [3, 2, 1], [4, 0, 0], [0, 1, 1]],
    # [[1, 1, 0], [2, 0, 1], [4, 2, 2]],
    # [[2, 0, 2], [5, 2, 0], [4, 1, 0], [1, 2, 1], [3, 0, 2]],
    # [[0, 1, 0], [0, 0, 1]],
]
s = Solution()
for c in cs:
    print(s.getMaximumNumber(c))

tfile = test_file_path(__file__, 1)

for _ in range(8):
    tcase = []
    for _ in range(5):
        tcase.append([random.randint(0, 7), random.randint(0, 2), random.randint(0, 2)])
    print(tcase, file=tfile)
# i = 0
# t = 1
# while t < 10**5:
#     t = 1 << i
#     i += 1
# print(i, t)
